package com.ly.algorithm.DataStructures.sort;

import java.util.Date;
import java.util.Random;

/**
 * @Classname ShellSort
 * @Description TODO
 * @Date 2020/4/24 13:51
 * @Author 冷心影翼
 */
public class ShellSort {

    public static void main(String[] args) {
//        int[] arr=  {3,202,-21,23,34,34,56,7,13,23,77};

        int[] arr = new int[800000];
//
        Random random = new Random();
        for(int i=0;i<800000;i++) {
            arr[i] =  random.nextInt(800000);
        }

        Date date1 = new Date();
        int groupCount = arr.length/2;
        while (groupCount>0) {
            for(int i=groupCount;i<arr.length;i++) {
                for (int j = i-groupCount; j >= 0; j-=groupCount) {
                    if(arr[j]>arr[j+groupCount]) {
                        int temp = arr[j];
                        arr[j] = arr[j+groupCount] ;
                        arr[j+groupCount] = temp;
                    }
                    else {
                        break;
                    }
                }
            }
            groupCount /=2;
        }


        Date date2 = new Date();
        System.out.println(date2.getTime()-date1.getTime());
//        System.out.println(Arrays.toString(arr));
    }
}
